package com.gitee.feizns.explore.data_structure.tree.bs.easy;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author feizns
 * @since 2019/12/9
 */
public class PreOrderTraversal {

    public static List<Integer> preOrderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        if ( root != null )
            stack.push(root);
        while ( !stack.isEmpty() ) {
            TreeNode node = stack.pop();
            ret.add(node.val);
            if ( node.right != null )
                stack.push(node.right);
            if ( node.left != null )
                stack.push(node.left);
        }
        return ret;
    }

    private static List<Integer> preOrderTraversal(List<Integer> list, TreeNode node) {
        if ( node != null ) {
            list.add(node.val);
            preOrderTraversal(list, node.left);
            preOrderTraversal(list, node.right);
        }
        return list;
    }

}
